//
// Created by guanyicheng on 2022/3/10.
//

#include "../../common.h"

struct MyListNode {
    int val;
    MyListNode *next;
    MyListNode *pre;

    MyListNode() : val(0), next(nullptr) {}

    MyListNode(int x) : val(x), next(nullptr) {}

    MyListNode(int x, MyListNode *pre, MyListNode *next) : val(x), pre(pre), next(next) {}
};

class MyLinkedList {

private:
    MyListNode *head;
    int size;

    MyListNode *getPtr(int index) {
        auto i = head->next;
        while (index-- > 0) {
            i = i->next;
        }
        return i;
    }

    void init(int val) {
        head->next = new MyListNode(val);
        head->next->next = head->next;
        head->next->pre = head->next;
        ++size;
    }

public:
    MyLinkedList() {
        head = new MyListNode();
        size = 0;
    }

    int get(int index) {
        if (index + 1 > size) {
            return -1;
        }
        return getPtr(index)->val;
    }

    void addAtHead(int val) {
        if (size == 0) {
            init(val);
        } else {
            auto temp = head->next;
            head->next = new MyListNode(val);
            temp->pre->next = head->next;
            head->next->pre = temp->pre;
            temp->pre = head->next;
            head->next->next = temp;
            ++size;
        }
    }

    void addAtTail(int val) {
        if (size == 0) {
            init(val);
        } else {
            auto tail = head->next->pre;
            tail->next = new MyListNode(val);
            tail->next->pre = tail;
            tail->next->next = head->next;
            head->next->pre = tail->next;
            ++size;
        }
    }

    void addAtIndex(int index, int val) {
        if (index > size) {
            return;
        }
        if (size == 0) {
            init(val);
        } else if (index < 0) {
            addAtHead(val);
        } else if (index == size) {
            addAtTail(val);
        } else {
            auto temp = getPtr(index);
            temp->pre->next = new MyListNode(val);
            temp->pre->next->pre = temp->pre;
            temp->pre = temp->pre->next;
            temp->pre->next = temp;
            ++size;
            if (index == 0) {
                // 改变虚拟节点指向
                head->next = head->next->pre;
            }
        }
    }

    void deleteAtIndex(int index) {
        if (index + 1 > size) {
            return;
        }
        auto rm = getPtr(index);
        if (index == 0) {
            head->next = head->next->next;
        }
        rm->pre->next = rm->next;
        rm->next->pre = rm->pre;
        delete rm;
        --size;
    }
};

int main() {
    MyLinkedList list{};
    list.addAtIndex(0, 10); // 10
    list.addAtIndex(0, 20); // 20 -> 10
    list.addAtIndex(1, 30); // 20 -> 30 -> 10
    list.get(0); // 20
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */